/*
 * TwoApprDfs.cpp
 *
 *  Created on: 14 nov. 2011
 *  Authors: bnoleau, cybourdi, rlecrois
 */

#include "TwoApprDfs.h"

TwoApprDfs::TwoApprDfs() {
}

TwoApprDfs::~TwoApprDfs() {
}

list<int> TwoApprDfs::vertexCover(Graph* g) {
	list<int> cover;
		if (g->numberOfNode() > 0)
			cover = selectNodesExceptEmpty(depthSearch(g));
	return cover;
	
}

Graph* TwoApprDfs::depthSearch(Graph* g) {

	map<int, int> nodesColor;
	Factory* f = Factory::getInstance();
    	Graph* aGraph = f->createGraphWithoutEdge(g->numberOfNode());

	for (int i=0 ; i < g->numberOfNode(); i++)
		markColor(g->nodeAt(i), WHITE, nodesColor);

	Node* u = g->nodeAt(0);
	stack<Node*> *p = new stack<Node*>();
	p->push(u);

	while (!p->empty()) {
		u = p->top();
		p->pop();
		if (!isColor(u, BLACK, nodesColor))
			markColor(u, BLACK, nodesColor);
	    for(list<Node*>::iterator it = u->getEdgeList()->begin(); it!=u->getEdgeList()->end(); ++it) {
	    	if (!isColor(*it, BLACK, nodesColor)) {
	    		markColor(*it, GREY, nodesColor);
	    		p->push(*it);
	    		aGraph->nodeAt(u->getID()-1)->getEdgeList()->push_back(*it);
	    	}
	    }
	}
	
	for (int i=0 ; i < g->numberOfNode(); i++)
		if (!isColor(g->nodeAt(i), BLACK, nodesColor)) { 
			cout << "Graph is not connected and can't be resolved" << endl;
			return f->createGraphWithoutEdge(g->numberOfNode());		
		}
			
	return aGraph;
}

bool TwoApprDfs::isColor(Node* n, int color, map<int, int> &nodesColor){
	return (nodesColor[n->getID()] == color);
}

void TwoApprDfs::markColor(Node* n, int color, map<int, int> &nodesColor){
	nodesColor[n->getID()] = color;
}

list<int> TwoApprDfs::selectNodesExceptEmpty(Graph* g){
	list<int> cover;
	for (int i=0 ; i < g->numberOfNode(); i++)
		if (!g->nodeAt(i)->getEdgeList()->empty())
			cover.push_back(g->nodeAt(i)->getID());
	return cover;
}

